\section{A lazy greedy algorithm}\label{s:lazymms}

In this section we prove Theorem~\ref{thm:2eps} and present $\lazy$, a variant of $\MMS$ (Algorithm~\ref{alg:mms}) that is faster by a factor $\Theta(k)$ and offers virtually the same approximation guarantee.

\begin{algorithm}[htb]
\SetAlgoLined
\KwData{Approval graph $G=(N\cup C, E)$, vector $s$ of vote strengths, committee size $k$, threshold support $t\geq 0$.}
Initialize $A=\emptyset$, $w=0\in\R^E$, and $U=C$ \;
\tcp{$U$ is set of ``uninspected'' candidates} 
\While{$U\neq \emptyset$}{
	Find $c_{\max}\in \argmax_{c'\in U} \score(c')$ \;
	\tcp{try unispected candidate of highest score} 
	Remove $c_{\max}$ from $U$\;
	Compute a balanced weight vector $w'$ for $A+c_{\max}$\;
	\If{$\supp_{w'}(A+c_{\max})\geq t$}{
		Update $A\leftarrow A+c_{\max}$ and $w\leftarrow w'$ \;
		\lIf{$|A|=k$} { \Return $(A,w)$}
	}
}
\Return a failure message\;
\caption{$\lazy$}
\label{alg:lazy}
\end{algorithm}

$\lazy$ (Algorithm~\ref{alg:lazy}) is lazier than $\MMS$ in the sense that for each candidate it inspects, it decides on the spot whether to add it to the current partial solution, if its insertion keeps the least member support above a certain threshold $t$, or permanently reject it. In particular, each candidate entails the computation of a single balanced weight vector, as opposed to $O(k)$ vectors in $\MMS$. 
For a threshold $t\geq 0$ given as input, the algorithm either succeeds and returns a full solution $(A,w)$ with $\supp_w(A)\geq t$, or returns a failure message. 
The idea is then to run trials of $\lazy$ over several input thresholds $t$, performing binary search to converge to a value of $t$ where it flips from failure to success, and return the output of the last successful trial. 
In terms of runtime, our binary search requires only $O(\log (1/\eps))$ trials -- as we shall prove -- and in each trial each of the $O(|C|)$ iterations computes a balanced weight vector in time $\bal$, for an overall complexity of $O(\bal\cdot |C| \log (1/\eps))$. 
In each iteration, the highest score in $U$ can be found in time $O(|E|\log k)$ with a variant of Algorithm $\maxscore$, hence this complexity is dominated by that of computing a balanced vector.  

We start by proving that for low values of $t$, the algorithm is guaranteed to succeed. 
We highlight that in the following proof the order in which the candidate set $C$ is traversed is irrelevant. 

\begin{lemma}\label{lem:success}
If $(A^*, w^*)$ is an optimal solution to the given instance of maximin support, and $t^*=\supp_{w^*}(A^*)$, then for any input threshold $t$ with $0\leq t\leq t^*/2$, $\lazy$ is guaranteed to succeed.
\end{lemma}

\begin{proof}
Assume by contradiction that for some input threshold $t\leq t^*/2$, $\lazy$ fails. 
Thus, after traversing the whole candidate set $C$, the algorithm ends up with a partial solution $(A,w)$ with $|A|<k$ and $\supp_w(A)\geq t$. 
By Lemma~\ref{lem:2sols}, there must be a candidate $c'\in A^*\setminus A$ and a feasible solution $(A+c', w')$ such that $\supp_{w'}(A+c')\geq t$. 
Notice as well that for any subset $S$ of $A+c'$, vector $w'$ still provides it with a support of at least $t$, and consequently any balanced weight vector for $S$ also provides it with a support of at least $t$. 
This implies that at whichever point the algorithm inspected candidate $c'$, it should have included it in the then-current partial solution, which was a subset of $A$. Hence, $c'$ should be contained in $A$, and we reach a contradiction.
\end{proof}

Next, we establish the number of trials needed to achieve a solution within a factor $(2+\eps)$ from optimal for any $\eps>0$. 

\begin{lemma}\label{lem:lazybinary}
For any $\eps>0$, $O(\log(1/\eps))$ trials of $\lazy$ are sufficient to obtain a solution whose maximin support value is within a factor $(2+\eps)$ from optimal.
\end{lemma}

\begin{proof}
First, we need to compute a constant-factor estimate of the optimal objective value $t^*$. 
One way to do that is, of course, to execute $\phragmms$ (Algorithm~\ref{alg:balanced}), which provides an approximation guarantee of $\alpha=3.15$ and runs in time $O(\bal\cdot k)$.%
\footnote{In fact, it can be checked that the $\phragmms$ algorithm is equivalent to an execution of $\lazy$ with threshold $t=0$.} 
If $t$ is the objective value of its output, and we initialize the variables $t'\leftarrow t/2$, $t''\leftarrow \alpha\cdot t$, then $\lazy$ is guaranteed to succeed for threshold $t'$ and fail for $t''$. We keep these properties as loop invariants as we perform binary search with $\lazy$, in each iteration setting the new threshold value to the geometric mean of $t'$ and $t''$. This way, the ratio $t''/t'$ starts with a constant value $2 \alpha$, and is square-rooted in each iteration. 
By Lemma~\ref{lem:success}, to achieve a $(2+\eps)$-factor guarantee it suffices to find threshold values $t'<t''$ such that $\lazy$ succeeds for $t'$ and fails for $t''$ and whose ratio is bounded by $t''/t'\leq 1+\eps/2$, and return the output for $t'$. If it takes $T+1$ iterations for our binary search to bring this ratio below $(1+\eps/2)$, then $(2\alpha)^{1/2^T} > (1+\eps/2)$, so $T= O(\log (\eps^{-1} \log(\alpha))) = O(\log(\eps^{-1}))$. This completes the proof. 
\end{proof}

Finally, we prove that whenever Algorithm $\lazy$ succeeds and returns a full solution, this solution satisfies PJR. For this, we exploit the order in which we inspected the candidates. This completes the proof of Theorem~\ref{thm:2eps}. 

\begin{lemma}
For any input threshold $t$, at the end of each iteration of $\lazy$ we have that if $(A,w)$ is the current partial solution, then $\supp_w(A)\geq \max_{c'\in C\setminus A} \score_{(A,w)}(c')$. 
Therefore, if the algorithm succeeds and returns a full solution, this solution satisfies PJR.
\end{lemma}

\begin{proof}
The second statement immediately follows from the first one together with Lemma~\ref{lem:localopt}, hence we focus on proving the first statement. 
Fix an input threshold $t$ and some iteration of $\lazy$, and let $(A,w)$ be the partial solution at the end of it. 
We consider three cases. Case 1: If all candidates inspected so far have been added to the solution and not rejected, then up to this point the construction coincides with Algorithm $\phragmms$, and the claim follows by Lemma~\ref{lem:315localoptimality}. 
Case 2: Suppose the last iteration was the first to reject a candidate, and let $c'$ be this candidate. Then, $c'$ has the highest score in $C\setminus A$, and we claim that this score must be below threshold $t$, and hence below $\supp_w(A)$. Otherwise, by Lemma~\ref{lem:insert} we have that Algorithm $\ins(A,w,c',t)$ could find a weight vector that gives $A+c'$ a support above $t$, so a balanced weight vector would also give $A+c'$ a support above $t$ which contradicts the fact that $c'$ was rejected. 
Case 3: If a candidate was rejected in a previous iteration, then at the time of the first rejection we had that the highest score in $C\setminus A$ was below $t$, and this inequality must continue to hold true in further iterations by Lemma~\ref{lem:2balanced}, because scores can only decrease. This completes the proof.
\end{proof}